The invention relates generally to information processing systems, and more specifically to an improved method for scan-converting a line for use with a graphical output in an information processing system.
A scan-conversion procedure for lines computes the coordinates of the pixels that lie on or near an ideal, thin straight line imposed on a two-dimensional grid (Foley, J. D. et al, Computer Graphics, 2d ed., 1996, Addison-Wesley, pp. 72-81).
The simplest procedure for the scan-conversion of a line computes the slope of the line and predicts the y-intercepts of the ideal line as the x-coordinate is repeatedly incremented by 1. A pixel is then intensified nearest the predicted y-intercept at the equally spaced x-increments.
The drawbacks of this simple procedure are that it involves floating point arithmetic and rounding and floor functions. Bresenham (Bresenham, J. E., xe2x80x9cAlgorithm for Computer Control of a Digital Plotter,xe2x80x9d IBM Systems Journal, 4(1), 1965, pp. 25-30) developed an algorithm that uses only integer arithmetic. Bresenham showed that his procedure provides a best-fit approximation to an ideal line by minimizing the error to the line. A floating point version of the Bresenham procedure can be applied to lines having arbitrary real-valued endpoint coordinates (Foley, supra, at p. 75).
Current graphical outputs in information processing systems demand the use of floating point arithmetic including multiply and divide operations to obtain needed accuracy. What is needed is a line scan-conversion procedure for application to lines having arbitrary real-valued endpoint coordinates in which floating point arithmetic is not required and in which many integer multiply and divide operations can be implemented using simple, fast left and right shift operations.
The present invention meets those needs, and others that will become apparent below, by providing a procedure for scan-converting a line, with an arbitrary precision, using integer arithmetic only. The procedure subdivides an integer grid into a new grid in which each original grid element is subdivided by a predetermined positive integer in both an X-direction and a Y-direction, where X and Y are orthogonal, rectangular coordinates. The original grid is referred to as an integer xe2x80x98coarsexe2x80x99 grid, while the subdivided grid is referred to as an integer xe2x80x98finexe2x80x99 grid. A line having arbitrary real-valued endpoint coordinates is defined in the fine grid system by providing a pair of integer vertices defining the opposite ends of the line. When the coarse grid granularity approximately equals an output pixel size, and when the fine grid granularity is approximately one-sixteenth that of the coarse grid, the method is able to accurately scan-convert lines having arbitrary real-valued endpoint coordinates without apparent loss of resolution.
Though the same result can be obtained using floating point arithmetic, the present invention uses only integer arithmetic and therefore does not need access to a floating point arithmetic unit. The Bresenham method (supra) can be implemented using only integer arithmetic, but it does not allow for arbitrary precision and is considered to be too slow for advanced graphic applications. The present procedure, on the other hand, is fast enough, and precise enough to meet the needs of the most demanding graphic display requirements.
The line scan-conversion procedure continues by ordering the two line-defining vertices such that the vertex having the larger integer Y-coordinate is referred to as the xe2x80x98largexe2x80x99 vertex, while the other vertex is the xe2x80x98smallxe2x80x99 vertex. The ordering will place the line into one of the first or the second quadrant depending on whether the slope of the line is negative or positive, respectively.
Having ordered the two vertices, the procedure will determine an integer approximation to a slope for an ideal line connecting the two vertices. The procedure will then increment in the Y-direction by one coarse grid unit and determine a best-fit X-coordinate in the fine grid system. The result will be a series of points defined relative to the fine grid and having Y-coordinates that coincide with coarse grid coordinates. The use of the fine grid coordinates in the X-direction produces the same results that can be obtained using floating point arithmetic while using [only] integer arithmetic only.
The results of the line scan-conversion procedure are used to adjust color and brightness attributes of display pixels. The resulting adjusted display pixels are output to a display device for creating an image of the scanned line segment.